package problem224_Basic_Calculator;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Solution {
	private static final Map<Character,Integer> operatorLevels=new HashMap<>();
	static {
		operatorLevels.put('+', 1);
		operatorLevels.put('-', 1);
		operatorLevels.put('(', 0);
		operatorLevels.put('#', -1);
	}
	
	 public int calculate(String s) {
		 char[] tokens=s.toCharArray();
		 Stack<Integer> operands=new Stack<>();
		 Stack<Character> operators=new Stack<>();
		 operators.push('#');
		 for(int i=0;i<tokens.length;i++){
			 if(Character.isDigit(tokens[i])){
				 int r=0;
				 while(i<tokens.length&&Character.isDigit(tokens[i])){
					 r=r*10+(tokens[i]-'0');
					 i++;
				 }
				 i--;
				 operands.add(r);
			 }else if(tokens[i]=='('){
				 operators.add('(');
			 }else if(tokens[i]==')'){
				 while(operators.peek()!='('){
					 operands.add(calculateBO(operands.pop(),operands.pop(),operators.pop()));
				 }
				 operators.pop();
			 }else if(tokens[i]==' '){
				
			 }else{
				 while(operatorLevels.get(operators.peek())>=operatorLevels.get(tokens[i])){
					 operands.add(calculateBO(operands.pop(),operands.pop(),operators.pop()));
				 }
				 operators.push(tokens[i]);
			 }
		 }
		 while(!operators.isEmpty()&&operators.peek()!='#'){
			 operands.add(calculateBO(operands.pop(),operands.pop(),operators.pop()));
			 operators.pop();
		 }
		return operands.peek();
	 }
	 
	 private int calculateBO(Integer o1, Integer o2, Character op) {
		 if(op=='+'){
			 return o1+o2;
		 }
		 return o2-o1;
	}
	 
	 public static void main(String[] args){
		 System.out.println(new Solution().calculate(" 2-1 + 2 "));
	 }
}
